package br.uece.comp.paa.entity;

import java.util.LinkedList;
import java.util.List;

import br.uece.comp.paa.entity.grafo.Aresta;
import br.uece.comp.paa.entity.grafo.Grafo;

/**
 * Implementação do Método Las Veas de forma a encontrar uma árvore de Custo
 * Máximo limitado a um parâmetro.
 * 
 * @author juliano
 * 
 */
public class Aleatorio extends GeradorArvoreMinima {

	public final int LIMITE_INTERACOES_ARVORE;

	public Aleatorio(Grafo g) {
		super(g);
		LIMITE_INTERACOES_ARVORE = g.getNumeroVertices()
				* g.getNumeroVertices()*1000;
	}

	@Override
	protected Grafo gerar(Grafo g, int grauMaximo, double custoMaximo) {
		boolean formouArvore = false;

		int verticeOrigem, verticeDestino;
		Double custo;
		List<Integer> verticesDentro = new LinkedList<Integer>();
		List<Integer> verticesFora = new LinkedList<Integer>();
		List<Aresta> arestas = new LinkedList<Aresta>();

		for (int v = 0; v < g.getNumeroVertices(); v++) {
			verticesFora.add(v + 1);
		}

		verticesDentro.add(sortearVertice(verticesFora));

		for (int i = 0; !formouArvore && i < LIMITE_INTERACOES_ARVORE; i++) {
			verticeOrigem = sortearVertice(verticesDentro);
			verticeDestino = sortearVertice(verticesFora);

			custo = g.getCusto(verticeOrigem - 1, verticeDestino - 1);
			if (custo != null) {
				if (respeitaRestricao(arestas, verticeOrigem - 1, grauMaximo)) {
					arestas.add(new Aresta(verticeOrigem - 1,
							verticeDestino - 1, custo));
					verticesDentro.add(verticeDestino);
					verticesFora.remove(new Integer(verticeDestino));

					if (verticesFora.size() == 0) {
						formouArvore = true;
					}
				} else {
					verticesDentro.remove(new Integer(verticeOrigem));
					i--;
				}
			} else {
				i--;
			}
		}

		Grafo result = g.extrairArvore(arestas);
		return result;

	}

	private int sortearVertice(List<Integer> vertices) {
		int indice = (int) (Math.random() * vertices.size() - 1);

		return vertices.get(indice);
	}

	private boolean respeitaRestricao(List<Aresta> arestas, int vertice,
			int grauMaximo) {
		int grauAtual = 0;
		boolean resultado = true;

		if (grauMaximo == 0 || grauMaximo == 1) {
			return true;
		}

		for (Aresta aresta : arestas) {
			if (aresta.getVertice1() == vertice
					|| aresta.getVertice2() == vertice) {
				grauAtual++;
			}
		}

		if (grauAtual >= grauMaximo) {
			resultado = false;
		}

		return resultado;
	}
}
